class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        // dp[i][j]表示在前i个数中选，刚好凑成j时的组合数
        // vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
        vector<int> dp(amount + 1);

        // dp[0][0]表示从0个硬币中选，恰好凑成0时的组合数，那就是0
        dp[0] = 1;

        // 下面是利用滚动数组做优化
        for(int i = 1; i <= n; i++)
            for(int j = coins[i - 1]; j <= amount; j++)
                dp[j] += dp[j - coins[i - 1]];
        return dp[amount];

        
        // for(int i = 1; i <= n; i++)
        // {
        //     for(int j = 0; j <= amount; j++)
        //     {
        //         dp[i][j] = dp[i - 1][j];
        //         if(j >= coins[i - 1])
        //             dp[i][j] += dp[i][j - coins[i - 1]];
        //     }
        // }
        // return dp[n][amount];
    }
};